package com.example.leetcode.prcatice;

import java.util.*;

/**
 * 给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。
 * 检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。
 *
 * 例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
 * 而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列，但不是最短的。
 * 如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。
 * 子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/ur2n8P
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer115 {


    // 拓扑排序
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        int n = nums.length;
        int[] penetration = new int[n + 1];
        Set<Integer>[] graph = new Set[n+1];
        for (int i=1;i<=n;i++){
            graph[i] = new HashSet<>();
        }
        for (int[]ints:sequences) {
            int size = ints.length;
            for (int i = 1;i<size;i++){
                int pre =ints[i-1];
                int next = ints[i];
                if (graph[pre].add(next)){
                    // 入度加加
                    penetration[next]++;
                }
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i =1;i<=n;i++) {
            if (penetration[i] == 0){
                queue.add(i);
            }
        }
        while (!queue.isEmpty()){
            // 入度大于1
            if (queue.size() >1){
                return false;
            }
            int i = queue.poll();
            Set<Integer> set = graph[i];
            for (int num:set) {
                penetration[num] --;
                if (penetration[num] == 0){
                    queue.add(num);
                }
            }
        }
        return true;
    }


    public static void main(String[] args) {
        Offer115 o = new Offer115();
        int[] nums = {1,2,3};
        int[][] sequences = {{1,2}};
        System.out.println(o.sequenceReconstruction(nums, sequences));

    }
}
